package com.atguigui.leetcode;

import java.util.ArrayDeque;

/**
 * 735.行星碰撞
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/7/13 9:32
 */
public class P735AsteroidCollision {
    public static void main(String[] args) {
        Solution solution = new P735AsteroidCollision().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        /**
         * 使用队列
         *
         * @param asteroids
         * @return
         */
        public int[] asteroidCollision(int[] asteroids) {
            ArrayDeque<Integer> stack = new ArrayDeque<>();

            for (int aster : asteroids) {
                boolean alive = true;
                //为负数，且栈不为空
                while (alive && aster < 0 && !stack.isEmpty() && stack.peek() > 0) {
                    //如果队列中头的比当前负的大，则不能放入队列
                    alive = stack.peek() < -aster; // aster 是否存在
                    if (stack.peek() <= -aster) {  // 栈顶行星爆炸
                        stack.pop();
                    }
                }
                //是否碰撞后需要放入队列
                if (alive) {
                    stack.push(aster);
                }

            }
            int size = stack.size();
            int[] ans = new int[size];
            for (int i = size - 1; i >= 0; i--) {
                ans[i] = stack.pop();
            }

            return ans;
        }
    }
}
